﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.DataStructures.Digraphs
{
    public class AdjacencyDigraph<T> : IEditableDigraph<T>        
    {
        protected readonly Func<IEnumerable<T>, IMap<T, Sets.ISet<T>>> _createMap;
        protected readonly Func<IEnumerable<T>, Sets.ISet<T>> _createSet;
        protected readonly Func<IMap<T, Sets.ISet<T>>, T, IMap<T, Sets.ISet<T>>> _redimensionMap;
        protected readonly Func<Sets.ISet<T>, T, Sets.ISet<T>> _redimensionSet;

        protected readonly bool _directed;
        private readonly VertexSet _vertexSet;
        private readonly EdgeSet _edgeSet;

        protected IMap<T, Sets.ISet<T>>_succs;
        private readonly EqualityComparison<T> _equalityComparison;

        public AdjacencyDigraph(IEnumerable<T> vertices = null, IEnumerable<Tuple<T, T>> edges = null,
                                 bool directed = true, 
                                 EqualityComparison<T> equalityComparison = null,
                                 Func<IEnumerable<T>, IMap<T, Sets.ISet<T>>> createMap = null,
                                 Func<IEnumerable<T>, Sets.ISet<T>> createSet = null, 
                                 Func<IMap<T, Sets.ISet<T>>, T, IMap<T, Sets.ISet<T>>> redimensionMap = null,
                                 Func<Sets.ISet<T>, T, Sets.ISet<T>> redimensionSet = null)
        {
            _createMap = createMap ?? (items => AlgoritmiaFactory.Maps<T, Sets.ISet<T>>.Default);
            _createSet = createSet ?? (items => AlgoritmiaFactory.Sets<T>.Default);
            _redimensionMap = redimensionMap ?? ((map, key) => map);
            _redimensionSet = redimensionSet ?? ((set, key) => set);
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
            _directed = directed;

            edges = edges ?? Enumerable.Empty<Tuple<T, T>>();
            edges = edges.ToList();

            vertices = vertices ?? (from e in edges
                                    select e.Item1).Concat(from e in edges
                                                           select e.Item2);

            _succs = _createMap(vertices);
            foreach (var v in vertices)
            {
                _succs[v] = _createSet(vertices);
            }

            foreach (var tuple in edges)
            {
                _succs[tuple.Item1].Add(tuple.Item2);
            }

            if (!_directed)
            {
                AddReversedEdges();
            }
            _vertexSet = new VertexSet(this);
            _edgeSet = new EdgeSet(this);

        }

        public AdjacencyDigraph(IEnumerable<KeyValuePair<T, IEnumerable<T>>> edges,
                                 bool directed = true, EqualityComparison<T> equalityComparison = null, 
                                 Func<IEnumerable<T>, IMap<T, Sets.ISet<T>>> createMap = null,
                                 Func<IEnumerable<T>, Sets.ISet<T>> createSet = null, Func<IMap<T, Sets.ISet<T>>, T, IMap<T, Sets.ISet<T>>> redimensionMap = null,
                                 Func<Sets.ISet<T>, T, Sets.ISet<T>> redimensionSet = null)
        {
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
            _createMap = createMap ?? (items => AlgoritmiaFactory.Maps<T, Sets.ISet<T>>.Default);
            _createSet = createSet ?? (items => AlgoritmiaFactory.Sets<T>.Default);
            _redimensionMap = redimensionMap ?? ((map, key) => map);
            _redimensionSet = redimensionSet ?? ((set, key) => set);
            _directed = directed;

            edges = edges ?? Enumerable.Empty<KeyValuePair<T, IEnumerable<T>>>();

            if (!(edges is IMap<T, IEnumerable<T>> || edges is IDictionary<T, IEnumerable<T>>))
            {
                edges = edges.ToDictionary(v => v.Key, v => v.Value);
            }
           
            _succs = _createMap(from e in edges
                                select e.Key);

            foreach (var kv in edges)
            {
                _succs[kv.Key] = _createSet(kv.Value);
                foreach(var elem in kv.Value)
                {
                    _succs[kv.Key].Add(elem);
                }
            }

            if (!_directed)
            {
                AddReversedEdges();
            }

            _vertexSet = new VertexSet(this);
            _edgeSet = new EdgeSet(this);

        }

        private void AddReversedEdges()
        {

            foreach (var kv in _succs)
            {
                foreach (var item in kv.Value)
                {
                    _succs[item].Add(kv.Key);
                }
            }

        }

        #region IEditableDigraph<T> Members

        public IEditableVertexSet<T> V
        {
            get { return _vertexSet; }
        }

        public IEditableEdgeSet<T> E
        {
            get { return _edgeSet; }
        }

        public bool IsDirected
        {
            get { return _directed; }
        }

        public IEnumerable<T> Successors(T vertex)
        {
            return _succs[vertex];
        }

        public virtual IEnumerable<T> Predecessors(T vertex)
        {
            return from kv in _succs
                   where kv.Value.Contains(vertex) 
                   select kv.Key;
        }

        public int OutDegree(T vertex)
        {
            return _succs[vertex].Count;
        }

        public virtual int InDegree(T vertex)
        {
            return Predecessors(vertex).Count();
        }

        #endregion

        #region Inner Classes

        public class VertexSet : IEditableVertexSet<T>
        {
            private readonly AdjacencyDigraph<T> _graph;

            public VertexSet(AdjacencyDigraph<T> graph)
            {
                _graph = graph;
            }

            #region IEditableVertexSet<T> Members

            public void Add(T vertex)
            {
               _graph.AddVertex(vertex);
            }

            public bool Remove(T vertex)
            {
                return _graph.RemoveVertex(vertex);
            }

            #endregion

            #region IVertexSet<T> Members

            public bool Contains(T item)
            {
                return _graph._succs.Contains(item);
            }

            #endregion

            #region IEnumerable<T> Members

            public IEnumerator<T> GetEnumerator()
            {
                foreach(var kv in _graph._succs)
                {
                    yield return kv.Key;
                }
            }

            #endregion

            #region IEnumerable Members

            System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
            {
                return GetEnumerator();
            }

            #endregion

            #region ICountable Members

            public int Count
            {
                get { return _graph._succs.Count; }
            }

            #endregion
        }

        public class EdgeSet : IEditableEdgeSet<T>
        {

            private readonly AdjacencyDigraph<T> _graph;

            public EdgeSet(AdjacencyDigraph<T> graph)
            {
                _graph = graph;
            }

            #region IEditableEdgeSet<T> Members

            public void Add(Tuple<T, T> edge)
            {
                _graph.AddEdge(edge.Item1,edge.Item2);
            }

            public void Add(T vertex1, T vertex2)
            {
                _graph.AddEdge(vertex1,vertex2);
            }

            public bool Remove(Tuple<T, T> edge)
            {
                return _graph.RemoveEdge(edge.Item1, edge.Item2);
            }

            public bool Remove(T vertex1, T vertex2)
            {
                return _graph.RemoveEdge(vertex1, vertex2);
            }

            #endregion

            #region IEdgeSet<Tuple<T,T>> Members

            public bool Contains(Tuple<T,T> tuple)
            {
                return Contains(tuple.Item1, tuple.Item2);
            }


            public bool Contains(T vertex1, T vertex2)
            {
                return _graph._succs.Contains(vertex1) &&
                       _graph._succs[vertex1].Any(value => _graph._equalityComparison(vertex2,value));
            }

            #endregion

            #region IEnumerable<Tuple<T,T>> Members

            public IEnumerator<Tuple<T,T>> GetEnumerator()
            {
                return (from kv in _graph._succs from v in kv.Value select new Tuple<T, T>(kv.Key,v)).GetEnumerator();
            }

            #endregion

            #region IEnumerable Members

            System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
            {
                return GetEnumerator();
            }

            #endregion

            #region ICountable Members

            public int Count
            {
                get
                {
                    return (from kv in _graph._succs
                            select kv.Value.Count).Sum();
                }
            }

            #endregion

        }

        #endregion

        #region IDigraph<T> Members

        IVertexSet<T> IDigraph<T>.V
        {
            get { return _vertexSet; }
        }

        IEdgeSet<T> IDigraph<T>.E
        {
            get { return _edgeSet; }
        }

        #endregion

        public override string ToString()
        {
            var sb = new StringBuilder(String.Format("{0} <{1}> [ ", GetType().Name, typeof(T).Name));

            foreach(var kv in _succs)
            {
                sb.Append(String.Format("( {0} , {1} ) ,",kv.Key,kv.Value));
            }
            sb.Append("]");
            return sb.ToString();
        }

        protected virtual void AddVertex( T vertex)
        {
            if (!_succs.Contains(vertex))
            {
                _succs = _redimensionMap(_succs, vertex);
                _succs[vertex] = _createSet(V);
            }
        }

        protected virtual bool RemoveVertex( T vertex)
        {
            if (_succs.Remove(vertex))
            {
                foreach (var key in _succs.Keys())
                {
                    _succs[key].Discard(vertex);
                }
                return true;
            }
            return false;
        }

        protected virtual void AddEdge( T vertex1, T vertex2)
        {

            if (!_succs.Contains(vertex1))
            {
                AddVertex(vertex1);
            }

            if (!_succs.Contains(vertex2))
            {
                AddVertex(vertex2);
            }

            _succs[vertex1] = _redimensionSet(_succs[vertex1], vertex2);
            _succs[vertex1].Add(vertex2);

            
            if (!_directed)
            {
                _succs[vertex2] = _redimensionSet(_succs[vertex2], vertex1);
                _succs[vertex2].Add(vertex1);
            }
        }

        protected virtual bool RemoveEdge(T vertex1, T vertex2)
        {
            if (!_succs.Contains(vertex1) || !_succs.Contains(vertex2))
            {
                return false;
            }
            if (!_directed)
            {
                _succs[vertex2].Remove(vertex1);
            }    
            return _succs[vertex1].Remove(vertex2);
        }
    }
}
